package algorithm.middle;

import java.util.*;
import java.util.stream.Collectors;

/**
 * https://leetcode.cn/problems/maximum-product-of-word-lengths/?envType=daily-question&envId=2023-11-
 * <p>
 * 给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
 */
public class maxProduct318 {


    List<Set<Integer>> all = new ArrayList<>();

    public int maxProduct(String[] words) {
        //由小到大排序
        List<String> list = Arrays.stream(words).sorted(Comparator.comparing(String::length)).collect(Collectors.toList());
        //定位set集合
        for (String s : list) {
            Set<Integer> currentSet = new HashSet<>();
            for (char c : s.toCharArray()) {
                currentSet.add((int) c);
            }
            all.add(currentSet);
        }
        int max = 0;
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                if (hasSameLetter(all.get(i), all.get(j))) {
                    continue;
                }
                max = Math.max(max, list.get(i).length() * list.get(j).length());
            }
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(5&2);
    }


    private boolean hasSameLetter(Set<Integer> setA, Set<Integer> setB) {
        if (setA.size() > setB.size()) {
            return setB.stream().anyMatch(setA::contains);
        } else {
            return setA.stream().anyMatch(setB::contains);
        }
    }


    /**
     *   作者：宫水三叶
     *     链接：https://leetcode.cn/problems/maximum-product-of-word-lengths/solutions/1105955/gong-shui-san-xie-jian-dan-wei-yun-suan-cqtxq/
     *     来源：力扣（LeetCode）
     *     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param words
     * @return
     */

    public int maxProduct2(String[] words) {
        int n = words.length, idx = 0;
        int[] masks = new int[n];
        for (String w : words) {
            int t = 0;
            for (int i = 0; i < w.length(); i++) {
                int u = w.charAt(i) - 'a';
                t |= (1 << u);
            }
            masks[idx++] = t;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if ((masks[i] & masks[j]) == 0) ans = Math.max(ans, words[i].length() * words[j].length());
            }
        }
        return ans;
    }


}
